package com.mokairui.sort.advanced;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

/**
 * @Description 归并排序
 * @Author Mokairui
 * @Since 2021/10/10
 */
@Slf4j(topic = "c.merge")
public class Merge {

    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 3, 2, 1};
        Merge.sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static int[] tempArray;

    private static void sort(int[] arr) {
        tempArray = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1);
    }

    /**
     * 自顶向下 递归
     * @param arr
     * @param start
     * @param end
     */
    private static void mergeSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }

        int mid = start + (end - start) / 2;
        mergeSort(arr, start,  mid);
        mergeSort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }

    /**
     * 从低智商 迭代
     * @param arr
     * @param start
     * @param end
     */

    private static void merge(int[] arr, int start, int mid, int end) {
        System.arraycopy(arr, start, tempArray, start, end - start + 1);
        int left = start;
        int right = mid + 1;

        for (int i = start; i <= end; i ++) {
            if (left > mid) {
                arr[i] = tempArray[right ++];
            } else if (right > end) {
                arr[i] = tempArray[left ++];
            } else if (tempArray[left] > tempArray[right]) {
                arr[i] = tempArray[right ++];
            } else {
                arr[i] = tempArray[left ++];
            }
        }
    }

}
